package middle;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import util.PrintUtils;

public class Solution_684 {

    private int[] arrays;
    private Set<Integer>[] sets;

    public int[] findRedundantConnection(int[][] edges) {
        arrays = new int[1001];
        sets = new Set[1001];
        for (int[] edge : edges) {
            Set<Integer> set0 = sets[edge[0]];
            if (set0 == null) {
                set0 = new HashSet<>();
            }
            set0.add(edge[1]);
            sets[edge[0]] = set0;

            Set<Integer> set1 = sets[edge[1]];
            if (set1 == null) {
                set1 = new HashSet<>();
            }
            set1.add(edge[0]);
            sets[edge[1]] = set1;
        }
        for (int i = edges.length - 1; i >= 0; i--) {
            Arrays.fill(arrays, -1);
            int[] edge = edges[i];
            dps(edges, edge[0], edge[0], edge[0], edge[1]);
            if (arrays[edge[1]] == edge[0]) {
                return edge;
            }
        }
        return null;
    }

    private void dps(int[][] edges, int index, int target, int a, int b) {
        if (arrays[index] == -1) {
            arrays[index] = target;
            Set<Integer> set = sets[index];
            if (set == null) {
                return;
            }
            for (Integer nextIndex : set) {
                if (a == index && b == nextIndex) {
                    continue;
                }
                dps(edges, nextIndex, target, a, b);
            }
        }
    }

    public static void main(String[] args) {
        Solution_684 model = new Solution_684();
        PrintUtils.arrayInt(model.findRedundantConnection(new int[][]{{1, 2}, {1, 3}, {2, 3}}));
        PrintUtils.arrayInt(model.findRedundantConnection(new int[][]{{1,2}, {2,3}, {3,4}, {1,4}, {1,5}}));
//        PrintUtils.transfer("[[1,2], [2,3], [3,4], [1,4], [1,5]]");
    }
}
